package org.example.myleet.rosalind.suff;

import java.util.ArrayList;
import java.util.List;

/**
 * https://rosalind.info/problems/suff/
 * T(s) is a rooted tree having exactly n leaves.
 * Every edge of T(s) is labeled with a substring of s∗, where s∗ is the string formed by adding a placeholder symbol $ to the end of s.
 * Every internal node of T(s) other than the root has at least two children; i.e., it has degree at least 3.
 * The substring labels for the edges leading down from a node to its children must begin with different symbols.
 * By concatenating the substrings along edges, each path from the root to a leaf corresponds to a unique suffix of s∗.
 * 对于一个长度为n-1的字符串s，构造后缀树前，s的结尾需要添加美元符号（$）作为结尾标识，使其成为长度为n的字符串s*，对s*进行后缀树构建，其后缀树的几个特征点：
 * 1、构造前字符串s*长度为n，后缀树的子节点也恰好是n个
 * 2、每一条边一直延伸到叶子节点的路径所连起来的字符是s*的其中一个独特后缀
 * 3、后缀树中的每一个内部节点（非叶子节点）下面必须至少有2个子节点，换句话说每个内部节点的度至少为3
 * 4、每个内部节点下面的子节点的开头字符各不相同
 * 5、同2
 *
 * 本解法展示的是最直接的通过字典树压缩法产生的后缀树，复杂度O(n^2)
 */
public class Solution {
    public static void main(String[] args) {
//        String input = "ATAAATG$";
        String input = "AGTAGTCTTCGGCCCATAGACTGCTTTCCGCCGTCGACTTTTTGCCCCGAGCGTCTACACCGATCAGACCCATCTCTGAAACCCGTACCTAACGTTTCTTCGACTCTAGTCGTTGGTGTAAATTCGTAGGGCGTAGTTGCGCCCCCGACAAGCACAATTTGACGAGGCGACTCCAACGGAGTGGCGTATCCTGGACAGACCCCCGCAGGTCCGCCTTAGCAGTCCTTTCACCTAGCCTGAGCTGTGTGGATATTGGAACCCACTTGATCTCCGAGAAATACATTCTACAGGGCCTATTCTGTAGGGGAGCTAGACAAACAACATACTTGGACCCCCACCTGGCTGCGTTCATCTTACTGTCTAGAGCCGCACGGGTAGTGGCTGAATAGAGCTTTTAAGCTAAACAGAGTTTCAGCGTCATAATGGATAAAATAGACCGCAAAACGTGAAACGCTTGCAGGACAAGAAAGTACACTCCTTGCGTTAAGAAGGCTGCTCATGGCGGCAGTGAAGAGCCGCACTTGTTTTTACCAGTTCAGACTCATCAGAGGAACCCCAGGACAGGGGGGCACGTAACCCGTAGCTTCATTCGCGGATAATGAGAACGGTTGTGTTTGTCTGTAATCACTGCTCAGTCCCAGAATTACTGTTCAGCGCCTAAGCAGCGTAAATGGGTTAGTGTGGATTAGGAGGTTGTGCCCGGAAAGACTATAGCTAATCTCGGCTACTCGTCATAGCTCAAACCGCCCCAAGTGCGCCACCTCAGGCCGATAGGTGGTGCGGGGAATAGATACCTATTATAACGGACTCTGTCTTGTGTTATCTCAGGAACCGGCCGTCCCTGGAACGCAAGACGAGGCGCATCGGAATGAACTCTTAGATATCGT$";
        SuffixTreeNode root = new SuffixTreeNode("");
        for (int i = 0; i < input.length(); ++i) {
            addSuffixToTrieTree(root, input, i);
        }
        compressSuffixTree(root);
        printAllNodes(root);
    }

    /**
     * 将input的其中一个后缀加入到字典树中，后缀为从start开始的input后缀
     */
    private static void addSuffixToTrieTree(SuffixTreeNode parent, String input, int start) {
        SuffixTreeNode cur = parent;
        for (int i = start; i < input.length(); ++i) {
            String c = input.substring(i, i + 1);
            SuffixTreeNode next = null;
            if (null == cur.children) {
                cur.children = new ArrayList<>();
                next = new SuffixTreeNode(c);
                cur.children.add(next);
            } else if (cur.children.size() < 1) {
                next = new SuffixTreeNode(c);
                cur.children.add(next);
            } else {
                for (SuffixTreeNode child : cur.children) {
                    if (child.val.equals(c)) {
                        next = child;
                        break;
                    }
                }
                if (null == next) {
                    next = new SuffixTreeNode(c);
                    cur.children.add(next);
                }
            }
            cur = next;
        }
    }

    /**
     * 由后缀生成的字典树压缩变成后缀树，本质上是后序遍历
     */
    private static void compressSuffixTree(SuffixTreeNode parent) {
        if (1 > parent.children.size()) {
            //叶子节点
            return;
        }
        for (SuffixTreeNode child : parent.children) {
            //先压缩子节点
            compressSuffixTree(child);
        }
        //然后尝试压缩parent节点
        if (1 == parent.children.size()) {
            //如果parent节点只有一个子节点，则压缩，将子节点的值连接到本节点上，孙子节点全拿过来，然后删除子节点
            SuffixTreeNode child = parent.children.get(0);
            parent.val = parent.val + child.val;
            parent.children.clear();
            parent.children.addAll(child.children);
        }
    }

    private static void printAllNodes(SuffixTreeNode parent) {
        //后序遍历的方式打印所有的节点值以返回题目要求的答案
        for (SuffixTreeNode child : parent.children) {
            printAllNodes(child);
        }
        System.out.println(parent.val);
    }

    static class SuffixTreeNode {
        String val;
        List<SuffixTreeNode> children;

        public SuffixTreeNode(String val) {
            this.val = val;
            children = new ArrayList<>();
        }
    }
}
